///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode() {}
// *     ListNode(int val) { this.val = val; }
// *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
//
////归并方法
//class Solution {
//    public ListNode mergeKLists(ListNode[] lists) {
//        int n=lists.length;
//        return meger(lists,0,n-1);
//    }
//    public ListNode meger(ListNode[] lists,int l,int r){
//        if(r<l) return null;
//        if(r==l) return lists[l];
//
//        //平分数组
//        int mid=(l+r)/2;
//        ListNode cur1=meger(lists,l,mid);
//        ListNode cur2=meger(lists,mid+1,r);
//
//        //合并两个链表
//        return megerTwoList(cur1,cur2);
//    }
//    public ListNode megerTwoList(ListNode cur1,ListNode cur2){
//        ListNode newHead=new ListNode(0);
//        ListNode pre=newHead;
//        while(cur1!=null&&cur2!=null){
//            if(cur1.val<=cur2.val){
//                pre.next=cur1;
//                cur1=cur1.next;
//            }else{
//                pre.next=cur2;
//                cur2=cur2.next;
//            }
//            pre=pre.next;
//        }
//        while(cur1!=null){
//            pre.next=cur1;
//            cur1=cur1.next;
//            pre=pre.next;
//        }
//
//        while(cur2!=null){
//            pre.next=cur2;
//            cur2=cur2.next;
//            pre=pre.next;
//        }
//        return newHead.next;
//    }
//}